package Sort.Sort;

import java.util.ArrayList;
import java.util.Arrays;

public class Sort {

    public Sort() {}

    private static boolean isGreat(Comparable c1, Comparable c2) {
        //c1>c2返回正，否则返回负，相等为0
        return c1.compareTo(c2) > 0;
    }

    private static void exchange(Comparable[] c, int i, int j) {
        Comparable temp;
        temp = c[i];
        c[i] = c[j];
        c[j] = temp;
    }

    //region 冒泡排序
    /*  冒泡排序
        时间复杂度n²
        算法稳定性：稳定
    */
    public static void bubbleSort(Comparable[] c) {
        for (int i = c.length - 1; i > 0; i--) {
            for (int j = 0; j < i; j++) {
                if (isGreat(c[j], c[j + 1])) {//升序
                    //if (isGreat(c[j+1],c[j])) {//降序
                    //或if (!isGreat(c[j],c[j+1])) {//降序
                    exchange(c, j, j + 1);
                }
            }
        }
    }
    //endregion

    //region 选择排序
    /*  选择排序
        时间复杂度n²
        算法稳定性：不稳定
     */
    public static void selectionSort(Comparable[] c) {
        /*if里面频繁的交换，效率低下
        for (int i = 0; i < c.length; i++) {
            for (int j = i+1; j < c.length; j++) {
                if(isGreat(c[i],c[j])){//升序
                    exchange(c,i,j);
                }
            }
        }
        */
        for (int i = 0; i < c.length; i++) {
            int min = i;
            for (int j = i + 1; j < c.length; j++) {
                if (isGreat(c[min], c[j])) {//升序
                    min = j;//只赋值，记录下最小元素索引，提高效率
                }
            }
            //循环完毕后交换
            exchange(c, i, min);
        }
    }
    //endregion

    //region 插入排序
    /*  插入排序
        原理
        1.把数组分为两组，已排序和未排序（初始认为第一个元素已排序）
        2.找到未排序的第一个元素，向已排序的组中进行插入
        3.插入后，插入位置后面的 已经排序的 数整体后移
        （这一步的实现：将待排元素与已排元素比较，倒序遍历已排元素，发现比待排的大，就交换）
        时间复杂度：n²
        稳定性：稳定
     */
    public static void insertionSort(Comparable[] c) {
        for (int i = 1; i < c.length; i++) {
            for (int j = i - 1; j >= 0; j--) {
                if (isGreat(c[j], c[j + 1])) {
                    exchange(c, j, j + 1);
                } else {
                    break;
                }
            }
        }
    }
    //endregion

    //SeniorSort    下面为高级排序
    //region 希尔排序
    /*  希尔排序
        原理
        1.选定一个增长量h，下标为0、h、2h…的元素为同一组
        h的确定方法
            int h = 1;
            while(h < 数组长度/2){
                h = 2 * h + 1;
            }
        h的减小规则：h = h / 2;
        2.对同一组进行插入排序
        3.减小增长量(最小为1)，重复步骤2
        稳定性：不稳定
     */
    public static void shellSort(Comparable[] c) {
        //1.确定 h
        int h = 1;
        while (h < c.length) {
            h = 2 * h + 1;
        }
        //2.排序
        while (h >= 1) {
            //排序
            for (int i = h; i < c.length; i++) {
                //可以知道第一个index=0，第二个为h，插入排序从第二个开始，所以i=h
                //解释i++：这样可以遍历到每一组元素
                for (int j = i - h; j >= 0; j -= h) {
                    if (isGreat(c[j], c[j + h])) {
                        exchange(c, j, j + h);
                    } else {
                        break;
                    }
                }
            }
            //改变h的值
            h = h / 2;
        }
    }
    //endregion

    //region 归并排序
    /*  归并排序(对数组进行分组，再归并，归并的过程中排序)(分治思想)
        1.尽可能地将数组拆分为两个等长的子数组，在对子数组拆分，直到每个子数组长为1
        2.将相邻两个子组合并成一个大组
        3.重复步骤2，直到只有一个组
        稳定性：稳定
        时间复杂度nlogn（不管拆没拆分，都要比较n次，拆了之后一共又logn层，所以共nlogn）
     */

    //归并排序所需要的辅助数组
    private static Comparable[] assist;

    public static void mergeSort(Comparable[] c) {
        assist = new Comparable[c.length];
        int low = 0;
        int high = c.length - 1;
        mergeSort(c, low, high);
    }

    //对数组中部分元素进行排序
    private static void mergeSort(Comparable[] c, int low, int high) {
        //安全性检测
        if (high <= low) {//防止无限递归，当数组长为1时就会停止
            return;
        }
        //对数组进行分组
        int mid = low + (high - low) / 2;
        mergeSort(c, low, mid);
        mergeSort(c, mid + 1, high);
        //归并
        merge(c, low, mid, high);
    }

    //low~mid为一个子组，mid+1~high为一个子组，将这两个子组合并成有序的大组
    //就是把两个有序数组合并成一个新的有序数组
    private static void merge(Comparable[] c, int low, int mid, int high) {
        //1.定义三个指针，一个指向assist，另两个指向两个子数组
        int i = low;//指向assist
        int p1 = low;//指向左子组
        int p2 = mid + 1;//指向右子组
        //2.比较两个子数组中指针指向的数的大小
        while (p1 <= mid && p2 <= high) {
            if (isGreat(c[p2], c[p1])) {
                //assist[i++]=c[p1++];
                assist[i] = c[p1];
                i++;
                p1++;
            } else {
                //assist[i++]=c[p2++];
                assist[i] = c[p2];
                i++;
                p2++;
            }
        }
        //3.如果有一个数组结束，另一个数组后面的数直接放入assist
        while (p1 <= mid) {
            assist[i++] = c[p1++];
        }
        while (p2 <= high) {
            assist[i++] = c[p2++];
        }
        //4.将assist中的数复制到原数组
        for (int index = low; index <= high; index++) {
            c[index] = assist[index];
        }
    }
    //endregion

    //region 快速排序
    /*  快速排序(分治思想)
        1.设定一个分界值，将数组分为左右两部分
        2.左侧值都小于或等于分界值，右侧则为大于或等于
        3.对左右侧独立进行排序。则又可以将一侧数组使用此方法进行分组
        4.明显是一种递归，当左右侧子组排完后整个数组便有序了
        稳定性：不稳定
        时间复杂度：最优nlogn，最坏n²
     */
    public static void quickSort(Comparable[] c) {
        int low = 0;
        int high = c.length - 1;
        quickSort(c, low, high);
    }

    private static void quickSort(Comparable[] c, int low, int high) {
        if (high <= low) {//安全性检测
            return;
        }
        //1.分组
        int partition = partition(c, low, high);//返回分界值对应的索引
        //2.对左子组排序
        quickSort(c, low, partition - 1);//因为partition位置不用排了
        //3.对右子组排序
        quickSort(c, partition + 1, high);
    }

    //对数组c，从low到high进行分组，并返回分组界限对应的索引
    //一般把数组第一个元素作为分界值，移动元素，将数组分出左右组，partition返回分完后分界值对应的索引
    private static int partition(Comparable[] c, int low, int high) {
        /*  定义left和right指针，left往右走，找比分界值大的元素，right往左走，找比分界值小的元素
            都找到后交换，然后继续找，直到left>=right
         */
        int left = low;//为了后面算法的一致性
        int right = high + 1;//为了后面算法的一致性
        Comparable key = c[low];
        while (true) {
            while (isGreat(c[--right], key)) {
                if (right == low) {
                    break;
                }
            }
            while (isGreat(key, c[++left])) {
                if (left == high) {
                    break;
                }
            }
            if (left >= right) {//判断结束，一定要在找元素之后判断
                break;
            } else {
                exchange(c, left, right);
            }
        }
        //最后放分界值,一定要和right交换！
        exchange(c, low, right);
        return right;
    }

    //另一种partition方案
    private static int partition2(int[] a, int left, int right) {
        int x = a[left];//同样以第一个元素作为分隔
        int i = left + 1;
        int j = right;
        while (i <= j) {//i从左往右扫描，扫到比哨兵大的就和j交换
            if (a[i] > x) {
                int t = a[i];
                a[i] = a[j];
                a[j] = t;
                j--;
            } else i++;
        }
        int temp = a[left];
        a[left] = a[j];
        a[j] = temp;
        return j;//返回哨兵所在的索引
    }
    //endregion

    //region 基数排序
    /*  基数排序RadixSort
        空间换时间
        稳定性：稳定
        时间复杂度：非常快(只需要 最大元素的位数 * 数字的进制 即可)
     */
    public static void radixSort(int[] c) {
        //使用二维数组存放，每一个桶为一个一维数组
        int bucket[][] = new int[10][c.length];
        //记录每个桶中放了多少元素
        int[] bucketElementCount = new int[10];
        //获取到数组中最大数的位数
        int max = c[0];
        for (int i = 0; i < c.length; i++) {
            if (c[i] > max) {
                max = c[i];
            }
        }
        int maxLength = (max + "").length();
        for (int i = 0, div = 1; i < maxLength; i++, div *= 10) {
            for (int j = 0; j < c.length; j++) {
                //记录对应位数
                int digitOfElement = c[j] / div % 10;
                //放入对应桶中
                bucket[digitOfElement][bucketElementCount[digitOfElement]] = c[j];
                //该桶内元素个数++
                bucketElementCount[digitOfElement]++;
            }
            int index = 0;
            for (int j = 0; j < bucket.length; j++) {
                if (bucketElementCount[j] != 0) {
                    for (int k = 0; k < bucketElementCount[j]; k++) {
                        c[index++] = bucket[j][k];
                    }
                }
                //取完后把对应基数的count清零
                bucketElementCount[j] = 0;
            }
        }
    }
    //endregion

    //region 计数排序
    /*  计数排序 O(n+k),n为数组长度，k为数组中的最大元素。计数排序虽然快，但是空间复杂度可能很高
        用一句话概括：用辅助数组对数组中出现的数字计数，元素转下标，下标转元素
        假设元素均大于等于0，依次扫描原数组，将数组值k记录在辅助数组的k位上
        一次扫描辅助数组，如果不为0(为几就说明了数字出现了几次)，将其插入目标数组的空白处
        我们需要遍历一次原数组，再遍历一次辅助数组即可完成排序
        但是对于例如{1, 100000, 2}这样的数组，辅助数组就很大，但只有三个元素，空间太浪费
     */
    public static void countingSort(int[] a) {
        if (a.length == 0) return;
        //找出原数组中最大的元素
        int max = a[0];
        for (int i = 1; i < a.length; i++) {
            if (a[i] < 0) {//安全性检测
                System.out.println("计数排序不适用于元素小于0的情况");
                return;
            }
            max = Math.max(a[i], max);
        }
        int[] assist = new int[max + 1];
        Arrays.fill(assist, 0);
        //依次扫描原数组，将数组值k记录在辅助数组的k位上
        for (int i = 0; i < a.length; i++) {
            assist[a[i]]++;
        }
        int aIndex = 0;//用于回拷数组到原数组的"指针"
        for (int i = 0; i < assist.length; i++) {
            if (assist[i] != 0) {
                for (int j = 0; j < assist[i]; j++) {
                    a[aIndex++] = i;
                }
            }
        }
    }
    //endregion

    //region 桶排序
    /*  桶排序 O(n)~O(nlogn)
        初始化一些桶（数组），然后遍历原数组，将数字经过一定的方式映射到桶中（桶的下标）
        然后我们会发现，下标为 n-1 的桶中的元素一定会小于 n 桶中的元素
        （因为映射公式相同，所以大数映射结果也大）
        对每个桶中的元素进行排序，再收集每个桶的元素到原数组
     */
    public static void bucketSort(int[] a) {
        //这里映射公式参考旧金山大学的index = value * array.length / (maxValueInArray+1)
        //这个映射公式需要开辟和原数组一样大小的桶数组
        if (a.length == 0) return;
        ArrayList<Integer>[] bucket = new ArrayList[a.length];
        for (int i = 0; i < a.length; i++) {
            bucket[i] = new ArrayList<>();
        }
        //先找出最大元素
        int max = a[0];
        for (int e : a) {
            if (e < 0) {//暂时还不能排序负数元素，能力不够，正在努力解决
                System.out.println("不能含有负数");
                return;
            }
            max = Math.max(e, max);
        }
        //将元素映射到桶中
        for (int e : a) {
            int index = e * a.length / (max + 1);
            bucket[index].add(e);
        }
        //对桶内元素排序并回收
        int aIndex = 0;
        for (int i = 0; i < a.length; i++) {
            int size = bucket[i].size();
            if (size > 0) {
                Integer[] array = bucket[i].toArray(new Integer[size]);
                Arrays.sort(array);//由于这里的排序不是桶排序的重点，所以就用API来排序了
                for (int j = 0; j < array.length; j++) {
                    a[aIndex++] = array[j];
                }
            }
        }
    }
    //endregion

    //region 堆排序
    /*  堆排序 O(nlogn) 空间复杂度O(n)
        堆是一个完全二叉树结构，采用数组存储
        把传入的数组构建成堆，然后移除堆顶元素，再堆化，直到所有元素移除
     */
    public static void heapSort(int[] a) {
        int[] heap = Arrays.copyOf(a, a.length);
        int length = a.length;
        buildMinHeap(heap, length);
        int aIndex = 0;
        while (length > 0) {
            length--;//一个元素出堆，heap数组的逻辑长度减1
            swap(heap, length, 0);
            a[aIndex++] = heap[length];
            heapify(heap, 0, length);
        }
    }

    private static void buildMinHeap(int[] heap, int length) {
        for (int i = length / 2 ; i >= 0; i--) {
            heapify(heap, i, length);
        }
    }

    private static void heapify(int[] heap, int i, int length) {
        //这里数组下标从0开始，所以左右孩子分别为 2*i+1 和 2*i+2
        int lchild = i * 2 + 1;
        int rchild = i * 2 + 2;
        int min = i;
        if (lchild < length && heap[lchild] < heap[i]) min = lchild;
        if (rchild < length && heap[min] > heap[rchild]) min = rchild;
        if (min != i) {
            swap(heap, min, i);
            heapify(heap, min, length);
        }
    }

    private static void swap(int[] heap, int i, int j) {
        int temp = heap[i];
        heap[i] = heap[j];
        heap[j] = temp;
    }
    //endregion
}
